\documentclass[12pt, A4]{article}
\usepackage{enumerate}
\usepackage{amsmath}
\usepackage{graphicx}

%\numberwithin{equation}

\begin{document}
%
% paper title
% can use linebreaks \\ within to get better formatting as desired
\title{Novel Untraceable Authenticated Key Agreement Protocol Using Smart Cards}


\author{Chin-Chen Chang, Hai-Duong Le, Hao-Chuan Tsai, Chin-Hsiang Chang}% <-this % stops a space







% make the title area
\maketitle


\begin{abstract}
%\boldmath
The abstract goes here.
\end{abstract}

\section{Introduction}

In distributed computing, client-server model is a distributed application architecture that provides a convenient method to interconnect client applications to servers. Clients communicate with servers over computer networks which are normally insecure, especially in the case of Internet. Moreover, in many applications, it is required that communicating partners identify each other before exchanging information. Therefore, it is required to design a protocol that provides authenticity and confidentiality of communication in client-server model. There are many authenticated key agreement schemes proposed to fulfill the aforementioned requirements. Among them, password authentication key agreement schemes are widely used in combination with smart card \cite{1277870,Juang2004167,4531703,Juang20081238,4801688}. 

In this type of authenticated key agreement schemes, a registered user who knows a password and possesses a smart card issued by server can mutual authenticate and establish a secure communication channel with the server. In 2008, Juang et al. proposed a robust and efficient user authentication and key agreement scheme \cite{4531703} that provides mutual authentication, key agreement, identity protection at high performance. In 2009, Li et al. improved  Juang et al's scheme with initiator untraceability property  \cite{4801688} while reserving the efficiency. However, the latter scheme has weaknesses. First, since the scheme employs verification table in authenticating users, an adversary can bring down the entire system by modifying or destroying the content of verification table. Second, it is subject to off-line password guessing attack. Lastly, 

In this paper, we proposed a novel password authentication key agreement scheme that can provides mutual authentication, session key agreement, and initiator untracability properties. Moreover, the proposed scheme is proved secure and has better performance then Li et al's scheme. 

In 1981, a remote password authentication was proposed; the method uses the one-way hash chain to encrypt information and a password table at server side for user verification \cite{Lamport:1981:PAI:358790.358797}. However, systems with password table may subject to stolen verifier attack, password guessing attacks \cite{Lee:2004:CUA:974104.974106}. In 1990, Chang et al. proposed a password authentication scheme without verification tables. 
  

The notation used in this papers includes the following.

\begin{tabular} {l p{10cm}}
$U$ & is the user \\
$ID$ & is the identity of $U$ \\
$PW$ & is the password of $U$ \\
$S$ & is the remote server \\ 
$s$, $s_1$, $s_2$ & are long term secret keys of $S$ \\
$h(\cdot)$ & is a public one-way hash function \\
$E_s(\cdot)$/$D_s(\cdot)$ & is a secure symmetric encryption/decryption algorithm with the secret key $s$ \\
$N$, $r$ & are random numbers \\
$p$ & is a large prime number \\
$E_p$ & is an elliptic curve equation over $Z_p$ \\
$G$ & is a generator point of large order \\
($x$, $P_S$) & is the server's private/public key pair  based on elliptic curve cryptosystem  \\

\end{tabular}

\section{Cryptanalysis of Li et al's scheme}

\subsection{Review of Li et al's scheme}
In this section, we review Li et al's password-authenticated key agreement scheme in brief. The scheme has totally five phases: parameter generation, registration, precomputation, log-in and password-changing. 

\subsubsection{Parameter generation}
Li et al's scheme is based on hash function, symmetric encryption and elliptic curve discrete logarithm problem. The system needs to generates the following parameters:
\begin{itemize}
\item First, the server chooses a large prime $p$ and two field elements $a \in Z_p$ and $b \in Z_p$, where $a$ and $b$ must satisfy $4a^3+27b^2\pmod p$.
\item The server then finds a generator point $G$ of large order.
\item The server selects a random number $x$ as its private.
\item Lastly, the server computes the public key $P_S=xG$ and publishes the parameters $\{P_S, p, E_p,G\}$.
\end{itemize}

There are some assumptions regarding the sizes of the parameters used in the scheme as follows.
\begin{itemize}
\item Both the block size of the block cipher $E_s(\cdot)$ and the output of hash function $h(\cdot)$ are 128 bits.
\item The sizes of user identity $ID$ and card identity $CI$ are both 32 bits.
\item The sizes of all the random numbers used in the system are 64  bits.

\end{itemize}
\subsubsection{Registration phase}
The registration phase is performed once for each user in the following steps.
\begin{enumerate}[Step 1]
\item A user $U$ with identity $ID$ chooses a password $PW$, a random number $b$ and a random nonce $N_0 \in_R \{0,1\}^{64}$ . Then, he gives 
\begin{equation}
\label{1}
\tag{1}
\{ID, h(PW\|b),N_0\}
\end{equation}
to the server $S$ for registration. 

\item After receiving $\{ID, h(PW\|b), N_0\}$, the server creates the card identity $CI$, which is the number of the card issued to the user. The server stores $\{ID, CI, N_0\}$ in the server's registration table. $S$ issues the card to the user $U$; the card contains the following information

\begin{equation}
\label{2}
\tag{2}
\{b^{N_0}_{ID}, V_{ID},ID,CI\}
\end{equation}
where
$$TAG_0= h((ID\|CI\|N_0)\|((ID\|CI\|N_0) \oplus h(PW\|b)))$$
$$b^{N_0}_{ID}=E_s((ID\|CI\|N_0)\|((ID\|CI\|N_0) \oplus h(PW\|b))\|TAG_0)$$
$$V_{ID}=h(ID\|s\|CI)$$

\item Upon receiving the card, the user $U$ writes $b$ into the card memory; as a result, the card memory contains  $\{b^{N_0}_{ID}, V_{ID}, ID, CI, b\}$.
\end{enumerate}

\subsubsection{Precomputation phase}
In this phase, the smart card computes $e = rG, c=rP_s=rxG$ as points over $E_p$, where $r$ is a random number. $e$ and $c$ are stored in smart card memory for later use in authentication and key agreement.

\subsubsection{Log-in phase}
In order to authenticate with the server, user inserts his smart card into card reader and keys in his password. Then, the user's system communicates with the server to established authentication and key agreement as follows.
\begin{enumerate}[Step 1]
\item The card chooses a nonce $N_1 \in_R {0,1}^{64}$, and sends 

\begin{equation}
\label{3}
\tag{3}
\{b^{N_0}_{ID},E_{V_{ID}}(N_1\|e)\}
\end{equation}

to the server.
\item Upon receiving $\{b^{N_0}_{ID},E_{V_{ID}}(N_1\|e)\}$, the server $S$ obtains $ID$, $CI$, $N_0$, $h(PW\|b)$ by decrypting $b^{N_0}_{ID}$ and validates $\{ID,CI,N_0\}$ against the registration table. If $b^{N_0}_{ID}$ is valid, the server decrypts $E_{V_{ID}}(N_1\|e)$ to gains $N_1$ and $e$. Then, the server updates registration table by replacing $N_0$ with $N_1$; the entry for user $U$ in registration table becomes $\{ID,CI,N_1\}$. The server selects $u \in_R {0,1}^{64}$, and computes $$c=xe$$ and $$M_S=h(c\|u\|V_{ID})$$ 
Next, server sends to the card the message 
\begin{equation}
\label{4}
\tag{4}
\{Nb1, u \oplus h_{64}(b^{N_1}_{ID}),M_S\}
\end{equation}
where $h_{64}(b^{N_1}_{ID})$ is the first 64 bits of $h(b^{N_1}_{ID})$ and\\
$$TAG_1=h((ID\|CI\|N_1)\|((ID\|CI\|N_1) \oplus h(PW\|b)))$$
$$b^{N_1}_{ID}=E_s((ID\|CI\|N_1)\|((ID\|CI\|N_1) \oplus h(PW\|b))\|TAG_1)$$
$$Nb1=b^{N_1}_{ID} \oplus (h(N_1\|e\|1)\|h(N_1\|e\|2)\|h(N_1\|e\|3))$$

\item The smart card obtains $b^{N_1}_{ID}$ from $Nb1$ with the knowledge of $N_1$ and $e$. The card also derives $u$ from $u \oplus h_{64}(b^{N_1}_{ID})$; then, it verifies whether $h(c\|u\|V_{ID})$ is equal to $M_S$. If it is true, the card sends 
\begin{equation}
\label{5}
\tag{5}
M_U=h(h(PW\|b)\|V_{ID}\|c\|u)
\end{equation}
to server for authenticating itself.

\item The server verifies whether $M_U \stackrel{?}{=}h(h(PW\|b)\|V_{ID}\|c\|u)$ holds. If it holds, the server accepts the log-in request of user $U$. Thus,  the smart card and the server successfully authenticate each other and share a session key $k=h(V_ID\|c\|u)$.

\end{enumerate}

\subsubsection{Password changing phase}
Before changing password, a user needs to log-in and shares a session key with the server. Then, $U$ chooses a new password $PW^*$ and a new random string $b^*$. The card sends password-changing message 

\begin{equation}
\label{6}
\tag{6}
\{E_k((ID\|CI\|N^*)\|h(PW^*\|b^*))\}
\end{equation}

to server, where $N^* \in_R {0,1}^{64}$.  

After receiving password-changing request, the server derives $ID$, $CI$, $N^*$, $h(PW^*\|b^*)$ by decrypting the cipher $\{E_k((ID\|CI\|N^*)\|h(PW^*\|b^*))\}$ using the session key $k$. The server $S$ updates the entry $\{ID,CI,N\}$ in the registration table with $\{ID,CI,N^*\}$. Then, the server sends to the user $U$ the response message 

\begin{equation}
\label{7}
\tag{7}
\{E_k(b^{N*}_{ID}\|ID\|CI\|N^*)\}
\end{equation}

where
$$TAG^*=h((ID\|CI\|N^*)\|((ID\|CI\|N^*) \oplus h(PW^*\|b^*)))$$
$$b^{N^*}_{ID}=E_s((ID\|CI\|N^*)\|((ID\|CI\|N^*) \oplus h(PW^*\|b^*))\|TAG^*)$$

Upon receiving the server's response, the smart card decrypts response message and verifies the extracted $ID$ and $CI$. After that, it replaces $b^{N}_{ID}$,$b$ with the newly derived values of $b^{N^*}_{ID}$,$b^*$ respectively. The password-changing procedure is accomplished and the smart card contains $\{b^{N^*}_{ID}$, $V_{ID}$, $ID$, $CI$, $b^*\}$ in its memory.

\subsection{Weakness of Li et al's scheme}
In this section, we present a weaknesses of Li et al's scheme. The scheme is susceptible to off-line password guessing attack, which allows attacker to obtain insecure low-entropy user's password with high probability.

Suppose that the attacker $A$ passively collects all the login phase messages (3), (4) and (5) between the user $U$ and the server $S$. $A$ then steals the smart card from the user $U$. As known in the studies \cite{Kocher1999,1004593}, it is possible for the attacker to extract stored secret values $\{b^{N_0}_{ID}$, $V_{ID}$, $ID$, $CI$, $b\}$ from a smart card as well as the values of $e$ and $c$ which were computed in precomputation phase and stored in the memory of the smart card. From the message (3), $A$ can use $V_{ID}$ to decrypt and obtain $N_1$. Using $N_1$ and $e$, the attacker can derive  $u$ from the message (4). At this stage, the attacker has known $V_{ID}$, $b$, $c$, and $u$. Now $A$ can obtain the password $PW$ of $U$ by guessing all possible password $PW'$ iteratively. For each $PW'$, the attacker computes $=h(h(PW'\|b)\|V_{ID}\|c\|u)$ and verifies the result  against the values of message (5), which is $M_U$. If there is $PW'$ that $h(h(PW'\|b)\|V_{ID}\|c\|u) = M_U$, the attacker has successfully guess the password of the user $U$ and uses $PW'$ to access to the server $S$.

The attack is possible because the shared secret $V_{ID}$ is unprotected in the smart card. We suggest that $V_{ID}$ should be stored securely in the smart card by masking (bit-wise XOR) it with $h(PW\|b)$ . 

\section{The proposed scheme}
In this section, we propose a new scheme that overcomes the weakness in Li et al's scheme. It also provides better performance comparing to Li et al's scheme. Moreover, the proposed scheme does not employ public key algorithm as in Li et al's scheme; thus, it does not required the public key management mechanism such as X.509. The proposed scheme consists of three phases: registration phase, login phase, and password-changing phase.

\subsection{Registration phase}
\begin{enumerate}[Step 1]
\item  A new user $U$ submits chooses his password $PW$ and a random number $r_0$; then, $U$ sends to server $S$ the request message

\begin{equation}
\label{1a}
\tag{1a}
\{ID,h(PW) \oplus r_0 \}
\end{equation}

for registration.

\item After receiving $\{ID,h(PW) \oplus r_0 \}$ from  $U$, server $S$ generates random number $r$ and computes the following parameters:
\begin{itemize}

\item $V = h(ID\|r)$
\item $IM = E_{s_1}(ID\|r) \oplus s_2  $,  where $E_{s_1}(\cdot)$ is a secure symmetric encryption function with the permanent secret key $s_1$. The random number $s_2$ is kept by the server $S$ as another long-term secret.

\item Server writes into the smart card the values

\begin{equation}
\label{2a}
\tag{2a}
\{V_1,IM\}
\end{equation}

where  $V_1=V  \oplus h(PW)  \oplus  r_0$; then, it issues the smart card to the user $U$.
\end{itemize}

\item When $U$ receives the smart card, he performs smart card activation in which $V_1$ is replaced by $V_2=V_1 \oplus r_0=V \oplus h(PW)$. After this stage, the memory of the card contains $\{V_2,IM\}$ and the card is ready for use in authentication.

Explaination: the random number $r_0$ is used only in registration phase. It masks the value of h(PW) so that we can prevent from insider attack \cite{1277863}.

\end{enumerate}

\subsection{ Login phase}
In this phase, the user $U$ and the server $S$ perform mutual authentication and establish a common session key. To enhance security of the scheme, we make an assumption that the $S$ will allow only a certain number of failed login attempts over a period of time. This assumption is made in order to prevent on-line dictionary attack when a valid smart card is either stolen or lost and falls into wrong hands - attackers. To establish mutual authentication and a shared-key, the smart card collaborates with the server in the following procedure.

\begin{enumerate}[Step 1] 
\item When user $U$ wants to login the server $S$, he inserts his smart card into the card reader and keys in his password $PW$. First, the smart card generates a random number $r_1$, derives $V$ from $V_2$, $V=V_2 \oplus h(PW)$, and computes $T_1=h(V \oplus r_1)$. Then, the card transmits the login request

\begin{equation}
\label{3a}
\tag{3a}
\{r_1,T_1,IM\} 
\end{equation}
to the server.

\item Upon receiving the login request message, $S$ uses its long-term secret keys $s_1$ and $s_2$ to decrypt $IM$, $D_{s_1}(IM \oplus s_2)= (ID \|r)$. Thus, it obtains $ID$ and $r$. $S$ then computes $V'=h(ID \| r)$ and verifies the request message by checking if $h(V' \oplus r_1)=T_1$ holds. In the case of inequality, the server $S$ rejects the user's login request and terminates the session. If the equality holds, the identity $ID$ of $U$ is authenticated, $S$ chooses a random numbers $r_{new}$ and computes new values of $V$ and $IM$ as follows.
\begin{itemize}
\item $V_{new}=h(ID\|r_{new})$
\item $IM_{new}=E_{s_1}(ID\|r_{new}) \oplus s_2$
\end{itemize}

Then, a random number $r_2$ is chosen by the server to compute and send to the card the response message 

\begin{equation}
\label{4a}
\tag{4a}
\{T_2=E_{V'}(r_2,IM_{new},V_{new},r_1)\} 
\end{equation}

\item The card decrypts $T_2$ and checks the integrity of $T_2$ by verifying the value of $r_1$ extracted from the cipher $T_2$.  If $r_1$ is invalid, the card terminates the session; otherwise, it believes that $T_2$ came from $S$ since the server $S$ can compute correct value of $V$ but no other can. The smart card also obtains $r_2$, $IM_{new}$, $V_{new}$ as the result of the decryption. And then it computes the session key $K=h(r_2\|V)$. The values of $IM$, $V_2$ in the card's memory are replaced by $IM_{new}$, $V_{new} \oplus h(PW)$ respectively. Finally, the card sends to the server $S$ the message

\begin{equation}
\label{5a}
\tag{5a}
\{T_3=h(K+1)\} 
\end{equation}

\item Upon receiving $T_3$, the server computes the session key $K'=h(r_2\|V')$ and verifies whether $h(K'+1)$ is equal to $T_3$. If it fails, the server closes the session to reject the failed login attempt; or else, the server accepts the log-in request.

\end{enumerate}

After the previous step, $S$ and $U$ have successfully authenticated each other and shared a session key $K$ for subsequent communication. Moreover, the scheme provides explicitly key confirmation since the server $S$ is assured that the user $U$ has computed the session key $K$ correctly, and no one other than $U$ can compute $K$.

\subsection{Password changing phase}
In this phase, it is required for the user to login before the password is changed. When the user $U$ wants to change his password, he inserts his smart card into card reader and enters his current password $PW$. First, the card authenticates the user against the server $S$. If the authentication is successful, the smart card requests the user to keys in his new password $PW_{new}$. Then, the card computes ${V_2}_{new} = V_2 \oplus h(PW) \oplus h(PW_{new})$. The last step is to replace $V_2$ with  ${V_2}_{new}$ in the smart card's memory. Finally, $U$ has successfully changed his password to $PW_{new}$.

\section{Evaluations of the proposed scheme}
\subsection{Security Analysis}
\subsubsection{Authenticated key agreement}
In 1990, Burrows, Abadi and Needham \cite{Burrows:1990:LA:77648.77649} formalized a method for logically analyzing protocols in computer networks. The method is widely known as BAN logic. It is used here to prove that the proposed scheme provides authentication and key agreement.   We need to prove that
$A$ \emph{believes} $S$ \emph{believes} $A \stackrel{K}{\longleftrightarrow}S$ and $S$ \emph{believes} $A$ \emph{believes} $A \stackrel{K}{\longleftrightarrow}S$, where $K$ is the session key.

We idealize the protocol as follows:
\begin{itemize}
\item \emph{Message 3a.} $A \rightarrow S$: $r_1, h(V,r_1), \{ID,r\}_{s_1}$
\item \emph{Message 4a.} $S \rightarrow A$: $\{r_2, IM_{new}, V_{new}, r_1\}_V$
\item \emph{Message 5a.} $A \rightarrow S$: $h(K)$ 
\end{itemize}

Since $S$ \emph{believes} $\stackrel{s_1}{\mapsto} S$, where $s_1$ is the secret key of $S$, and  $S$ \emph{sees} $\{ID,r\}_{s_1}$, so $S$ \emph{believes} $S$ \emph{said} ($ID, r$). Thus, $S$ \emph{believes} $V$, since $V=h(ID,r)$. Also, $S$ \emph{believes} $S \stackrel{V}{\rightleftharpoons}A$, because only $A$ with the correct password $PW$ can retrieve $V$ from his smart card. Analyzing message (3a) further, we get 

\begin{equation}
\label{4.1}
\tag{4.1}
S \text{ \emph{believes} } A \text{ \emph{said} }  r_1
\end{equation}
because $S$ \emph{believes} $S \stackrel{V}{\rightleftharpoons}A$ and $S$ \emph{sees} $h(V, r_1)$.

Upon receiving message (4a), the \emph{message-meaning rule} is applied and yields $A$ \emph{believes} $S$ \emph{said} ($r_2, IM_{new}, V_{new}, r_1$), since $A$ \emph{belives} $A \stackrel{V}{\longleftrightarrow}S$ and $A$ \emph{sees} $\{r_2$, $IM_{new}$, $V_{new}$, $r_1\}_V$. $r_1$ is a random number chosen by $A$ for the current session, thus $A$ \emph{believes} $fresh(r_1)$. According to the \emph{nonce-verification rule}, 
\begin{equation}
\label{4.2}
\tag{4.2}
A \text{ \emph{believes} } S \text{ \emph{believes} } r_2, IM_{new}, V_{new}
\end{equation}
therefore,
\begin{equation}
\label{4.3}
\tag{4.3}
A \text{ \emph{believes} } S \text{ \emph{believes} } A \stackrel{K}{\longleftrightarrow}S
\end{equation}
since $K=(r_2\|V)$.

When $S$ receives message (5a), the \emph{message-meaning rule} yields
\begin{equation}
\label{4.4}
\tag{4.4}
S \text{ \emph{believes} } A \text{ \emph{said} } K
\end{equation}
since $S$ \emph{believes} $A \stackrel{V}{\rightleftharpoons}S$ and $K=h(r_2\|V)$. Moreover, because $S$ \emph{believes} $r_2$ is \emph{fresh}; thus, the \emph{nonce-verification rule} yields
\begin{equation}
\label{4.5}
\tag{4.5}
S \text{ \emph{believes} } A \text{ \emph{believes} } A \stackrel{K}{\longleftrightarrow}S
\end{equation}

From the results (4.3) and (4.5), we conclude that the proposed scheme provides mutual authentication and key agreement between $A$ and $S$.

\subsection{Functionality Concerns}

\section{Conclusion}
The conclusion goes here.

\bibliographystyle{plain}
\bibliography{science}

\end{document}


